package leetcode;
import java.util.*;

public class LeetCodeMain77 {
    public int minPathSum(int[][] grid) {
        for (int i = 1; i < grid[0].length; i++) {
            grid[0][i]+=grid[0][i-1];
        }
        for (int i = 1; i < grid.length; i++) {
            grid[i][0]+=grid[i-1][0];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                grid[i][j]+=Math.min(grid[i][j-1],grid[i-1][j]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
    List<String> list=new ArrayList<>();
    StringBuffer buffer=new StringBuffer();
    public List<String> generateParenthesis(int n) {
        back(0,0,n);

        return list;
    }
    public void back(int leftN,int rightN,int n){
        if (buffer.length()==n*2){
            list.add(buffer.toString());
            return;
        }
        if (rightN<n){
            buffer.append('(');
            back(leftN, rightN+1, n);
            buffer.deleteCharAt(buffer.length()-1);
        }if (rightN>leftN){
            buffer.append(')');
            back(leftN+1, rightN, n);
            buffer.deleteCharAt(buffer.length()-1);
        }
    }
    public String longestPalindrome(String s) {
         String str="";
         int length=s.length();
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                if (isString(s,j,i-1)){
                    if (i-j>str.length()){
                        str=s.substring(j,i);
                    }
                    break;
                }
            }
        }
        return str;
    }
    public boolean isString(String s,int start,int end){
        while (start<=end){
            if (s.charAt(start)!=s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}
